package com.剑指Offer;

import java.util.Arrays;

/**
 * 用于快排的Partiton函数
 * @author qiuxiaochen
 *
 */
public class 快排实现Partition {
	
	public static int Partition(int []array,int start,int end){
		if(array==null||array.length==0)
			return -1;
		if(start<0||end>array.length-1||start>end)
			return -1;
		if(start==end){
			return end;
		}
		int temp=array[start];
		array[start]=array[end];
		array[end]=temp;
		
		int small=start-1;
		for (int i = start; i < end; i++) {
			if(array[i]<=array[end]){
				small++;
				if(small!=i){
					temp=array[i];
					array[i]=array[small];
					array[small]=temp;
				}
			}
		}
		small++;
		temp=array[end];
		array[end]=array[small];
		array[small]=temp;
		return small;
	}
	
	public static void quickSort(int[] array,int start,int end){
		if(array==null||array.length==0)
			return;
		if(start<0||end>array.length-1||start>=end)
			return;
		int index=Partition(array, start, end);
		quickSort(array, index+1, end);
		quickSort(array, start,index-1);
	}
	public static void main(String[] args) {
		int []xixi={10,2,6,10,40,50,23,22,4,4,7,8,9};
		quickSort(xixi, 0, xixi.length-1);
		System.out.println(Arrays.toString(xixi));
	}
}
